package org.shj.algorithm.yichuan;

import java.util.LinkedList;
import java.util.List;
import java.util.Random;

//问题描述： 有N 个城市， 找出遍访每个城市恰好一次的一条回路，使得其长度最短。即若从C1出发，遍访其它每个城市，并且只访问一次，最后回到C1，求最短总路径
//遗传算法得到的不一定是最优解，接近最优解的程度与初始设定的群体大小，终止条件，变异概率等因素有关
public class Tsp {
	
	public int initGroupSize = 60; //初始群体大小，一般取 20~100
	
	public int yiChuanSize = 30;
	
	public int cityCount = 9;
	
	public double jiaoChaRate = 0.5; //交叉概率，一般取 0.4 ~ 0.9
	
	public double bianYiRate = 0.05; //变异概率，一般取 0.0001 ~ 0.1
	
	public int calTimes = 200;   //进化多少代，一般取 100 ~ 500
	
	//各个城市间的距离
	public static int[][] d = new int[][]{
		{0, 1, 2, 3, 4, 5, 6, 7, 8},
		{1, 0, 2, 4, 7, 8, 6, 9, 3},
		{2, 2, 0, 3, 6, 9, 8, 5, 4},
		{3, 4, 3, 0, 9, 2, 1, 6, 8},
		{4, 7, 6, 9, 0, 5, 2, 9, 6},
		{5, 8, 9, 2, 5, 0, 4, 7, 9},
		{6, 6, 8, 1, 2, 4, 0, 3, 5},
		{7, 9, 5, 6, 9, 7, 3, 0, 7},
		{8, 3, 4, 8, 6, 9, 5, 7, 0}
	};
	
	
	public static void main(String[] args){
		Tsp tsp = new Tsp();
		List<Single> group = tsp.initGroup();
		tsp.process(group);
		
		System.out.println("************************");
		
		Single min = group.get(0);
		for(int i = 1 ; i < group.size() ; i++){
			if(calDis(group.get(i).getSin()) < calDis(min.getSin())){
				min = group.get(i);
			}
		}
		System.out.print("distance = " + calDis(min.getSin()) + ": ");
		print(min.getSin());
		
		
//		Random r = new Random();
//		System.out.println(r.nextDouble());
//		System.out.println(r.nextDouble());
//		System.out.println(r.nextDouble());
	}
	
	private static void print(int[] val){
		for(int v : val){
			System.out.print(v + ", ");
		}
		System.out.println();
	}
	
	public void process(List<Single> group){
		calTimes--;
		System.out.println(calTimes + ", size: " + group.size());
		
		//计算适应度
		calFitness(group);
		
		//选择操作
		select(group);
				
		//交叉操作
		crossover(group);
		
		//变异操作
		mutation(group);
		
		if(!isTerminate(group)){
			process(group);
		}
	}
	
	//初始化种群
	private List<Single> initGroup(){
		List<Single> group = new LinkedList<Single>();
		for(int i = 0 ; i < initGroupSize; i++){
			group.add(genSingle());			
		}
		return group;
	}
	
	private void calFitness(List<Single> group){
		for(int i = 0 ; i < group.size() ; i++){
			calShiYingDu(group.get(i));
		}
	}
	
	private void select(List<Single> group){
		Single sin = null;
		List<Single> sortGroup = new LinkedList<Single>();		
		while(group.size() > 1){
			int min = 0;
			for(int i = 1 ; i < group.size(); i++){
				if(group.get(i).getShiYingDu() < group.get(min).getShiYingDu()){
					min = i;
				}
			}
			
			sortGroup.add(group.remove(min));
		}
		sin = group.get(0);
		sortGroup.add(sin);
		group.clear();
		
		for(int j = 0 ; j < yiChuanSize; j++){				
			group.add(sortGroup.get(j));
		}
	}
	
	//使用赌盘选择法
	/*
	private void select(List<Single> group){
//		System.out.println("==== select ====");
		//获得各个适应度的总和，用于计算概率
		double total = 0;
		Single sin = null;
		for(int i = 0 ; i < group.size(); i++){
			sin = group.get(i);
			boolean flag = false;
			for(int j = 0; j < i ; j++){
				if(sin.getShiYingDu() == group.get(j).getShiYingDu()){
					flag = true;
					break;
				}
			}
			if(!flag){
				total += sin.getShiYingDu();
			}
		}
//		System.out.println("==== select 111 ====");
		for(int i = 0 ; i < group.size(); i++){
			sin = group.get(i);
			sin.setRate(sin.getShiYingDu() / total);
		}
		
		//按适应度排序, 并计算累积机率, 适应度（距离总长）越大，选择的机率应越小
		List<Single> sortGroup = new LinkedList<Single>();		
		while(group.size() > 1){
			int max = 0;
			for(int i = 1 ; i < group.size(); i++){
				if(group.get(i).getShiYingDu() > group.get(max).getShiYingDu()){
					max = i;
				}
			}
			
			if(!sortGroup.isEmpty()){
				sin = group.remove(max);
				sin.setRate(sin.getRate() + sortGroup.get(sortGroup.size() - 1).getRate());
			}
			sortGroup.add(sin);
		}
		sin = group.get(0);
		sin.setRate(1); //最后一个的累积概率肯定是 100%
		sortGroup.add(sin);
		group.clear();
		
//		System.out.println("==== select 222====");
		
		Random r = new Random();
		double rate = 0;
		while(group.size() < yiChuanSize){			
			rate = r.nextDouble();
			for(int j = 0 ; j < sortGroup.size(); j++){				
				sin = sortGroup.get(j);
				if(rate < sin.getRate()){ 
					group.add(sortGroup.remove(j));
					break;
				}
			}
		}
//		System.out.println("==== select end====");
	}*/
	
	private void crossover(List<Single> group){
//		System.out.println("==== jiaoCha() ====");
		Random r = new Random();
		List<Single> parent = new LinkedList<Single>();
		
		//按概率选择双亲
		for(int i = 0 ; i < group.size(); i++){
			if(r.nextDouble() > jiaoChaRate){
				parent.add(group.get(i));
			}
		}
		
		//双亲两两交叉
		int[] p1 = null;
		int[] p2 = null;
		int[] p11 = null;
		int[] p21 = null;
		int[] A = null;
		int[] B = null;
		int f1 = 0; //交叉起始点
		int f2 = 0;
		Single newSin = null;
		
		//group.clear();
		
		for(int i = 0 ; i < parent.size() - 1; i++){
			p1 = parent.get(i).getSin();
			p11 = new int[p1.length];
			p21 = new int[p1.length];
			
//			for(int j = i + 1 ; j < parent.size(); j++){
				p2 = parent.get(i+1).getSin();
//				System.out.println("### 交叉前 p1, p2");
//				print(p1);
//				print(p2);
				
				//随机产生两个交叉点
				f1 = r.nextInt(3) + 3; //保证交叉点至少从第3个位置开始并且不超过 cityCount - 2 的位置
				f2 = r.nextInt(cityCount - 2) + 2 ; 
				while(f1 == f2){
					f2 = r.nextInt(cityCount - 2) + 2 ; 
				}
				if(f1 > f2){
					int tmp = f1;
					f1 = f2;
					f2 = tmp;
				}
//				System.out.println("*** f1 = " + f1 + ", f2=" + f2);
				A = new int[f2-f1];
				B = new int[f2-f1];
				for(int k = f1; k < f2; k++){
					A[k - f1] = p1[k];
					B[k - f1] = p2[k];
				}
				
//				System.out.println("*** A, B ");
//				print(A);
//				print(B);
				
				//交叉[f1,f2)以外的值，生成新的染色体
				for(int k = 0 ; k < p1.length; k++){
					if(k < f1 || k >= f2){
						p11[k] = p2[k];
						p21[k] = p1[k];
					}else{
						p11[k] = p1[k];
						p21[k] = p2[k];
					}
				}
				
//				System.out.println("*** p11, p21 ");
//				print(p11);
//				print(p21);
				
				checkDulplicate(p11, A, B, f1, f2);
				checkDulplicate(p21, B, A, f1, f2);
				
//				System.out.println("--> p11, p21 ");
//				print(p11);
//				print(p21);
				
				newSin = new Single();
				newSin.setSin(p11);
				group.add(newSin);
				
				newSin = new Single();
				newSin.setSin(p21);				
				group.add(newSin);
//			}
		}
//		System.out.println("==== jiaoCha 111 ====");
		//选择较优的
		//select(group);
		
//		System.out.println("==== jiaoCha() end ====");
	}
		
	//比较交换区中的值（int[] p 中 0 ~ f1 和 f2 ~ 末尾位置的值）是否与未交换区(int[] a)中的某个值相同，若相同，则用int[] b中相应位置的值代替
	private void checkDulplicate(int[] p, int[] a, int[] b, int f1, int f2){
		boolean hasSame = false;
		do{
			hasSame = false;
			out:
			for(int k = 0 ; k < f1; k++){
				for(int i = 0 ; i < a.length; i++){
					if(p[k] == a[i]){
						p[k] = b[i];
						hasSame = true;
						break out;
					}
				}
				
			}
		}while(hasSame);
		
		do{
			hasSame = false;
			out:
			for(int k = f2 ; k < p.length; k++){
				for(int i = 0 ; i < a.length; i++){
					if(p[k] == a[i]){
						p[k] = b[i];
						hasSame = true;
						break out;
					}
				}
			}
		}while(hasSame);
	}
	
	private void mutation(List<Single> group){
//		System.out.println("==== bianYi ====");
		Random r = new Random();
		List<Single> bian = new LinkedList<Single>();
		
		//按概率选择双亲
		for(int i = 0 ; i < group.size(); i++){
			if(r.nextDouble() < bianYiRate){
				bian.add(group.get(i));
			}
		}
		
		int[] val = null;
		int k = 0;
		int v = 0;
//		System.out.println("==== bianYi 111====");
		
		for(Single sin : bian){
			val = sin.getSin();
//			System.out.println("########### pre");
//			print(val);
			k = r.nextInt(val.length);
			do{
				v = r.nextInt(val.length);
			}while(v == k);
			
			int tmp = val[k];
			val[k] = val[v]; //把V位置的值放入k位置
			
			//删除 v 位置的值，并把原来k位置的值放入末尾
			for(int i = v ; i < val.length - 1; i++){
				val[i] = val[i+1];
			}
			val[val.length - 1] = tmp;
//			System.out.println("########### after");
//			print(val);
			this.calShiYingDu(sin);
		}
		
//		System.out.println("==== bianYi end====");
	}
	
	private Single genSingle(){
		Tsp.Single s = new Tsp.Single();
		int[] single = new int[cityCount];
		List<Integer> sin = new LinkedList<Integer>();
		for(int i = 1 ; i <= cityCount ; i++){//1~9 代表第1～9个城市
			sin.add(i);
		}
		Random r = new Random();
		for(int i = 0; i < cityCount - 1; i++){
			int ind = r.nextInt(sin.size());
			single[i] = sin.get(ind);
			sin.remove(ind);
		}
		single[cityCount - 1] = sin.get(0);
		s.setSin(single);
		return s;
	}
	
	private void calShiYingDu(Single sin){
		int[] single = sin.getSin();
		
		sin.setShiYingDu(calDis(single));
	}
	
	private static int calDis(int[] single){
		int distance = 0;
		for(int i = 0 ; i < single.length - 1; i++){
			distance += d[single[i] - 1][single[i + 1] - 1];
		}
		distance += d[single[single.length - 1] - 1][single[0] - 1]; //从最后一个城市到出发城市的距离
		return distance;
	}
	
	public boolean isTerminate(List<Single> group){
		if(calTimes == 0){
			return true;
		}
		calShiYingDu(group.get(0));
		int pre = group.get(0).getShiYingDu();
		for(int i = 1 ; i < group.size(); i++){
			calShiYingDu(group.get(i));
			if(pre != group.get(i).getShiYingDu()){
				return false;
			}
		}
		return true;
	}
	
	public class Single{
		private int[] sin;
		private int shiYingDu;
		private boolean isSelected;
		private double rate;
		
		public int[] getSin() {
			return sin;
		}
		public void setSin(int[] sin) {
			this.sin = sin;
		}
		public int getShiYingDu() {
			return shiYingDu;
		}
		public void setShiYingDu(int shiYingDu) {
			this.shiYingDu = shiYingDu;
		}
		public boolean isSelected() {
			return isSelected;
		}
		public void setSelected(boolean isSelected) {
			this.isSelected = isSelected;
		}
		public double getRate() {
			return rate;
		}
		public void setRate(double rate) {
			this.rate = rate;
		}
		
		
	}
}
